package main

import (
	"fmt"
)

func combinationSum(candidates []int, target int) [][]int {
	if len(candidates) == 0 || target < 0 {
		return nil
	}

	if target == 0 {
		return [][]int{nil}
	}

	r := [][]int{}
	for _, c := range combinationSum(candidates, target-candidates[0]) {
		plusc := make([]int, len(c)+1)
		plusc[0] = candidates[0]
		copy(plusc[1:], c)
		r = append(r, plusc)
	}
	r = append(r, combinationSum(candidates[1:], target)...)
	return r
}

func main() {
	var candidates []int
	var target int

	candidates = []int{7}
	target = 7
	fmt.Println(combinationSum(candidates, target))

	candidates = []int{2, 3, 6, 7}
	target = 7
	fmt.Println(combinationSum(candidates, target))

	candidates = []int{2, 3, 5}
	target = 8
	fmt.Println(combinationSum(candidates, target))
}
